This invention relates to graphics systems, and more particularly to gamma correction of pixels.
Video displays using cathode-ray tubes (CRTs) are widely used. A voltage applied to the CRT determines the intensity or brightness of a pixel. As the applied voltage is increased, the pixel appears brighter as the CRT""s light output increases. However, the relationship of the applied voltage to the light output is not a simple linear function. Instead, the light output is proportional to the applied voltage raised to a power of a constant gamma (xcex3):
L=vxcex3
where v is the applied or driving voltage normalized between 0 and 1 and L is the light output. For television monitors, gamma xcex3 is typically between 2.2 to 2.8, while gamma is somewhat lower, between 1.4 and 2.2, for most computer monitors. Thus the light output is roughly the square of the normalized voltage.
A captured image, such as one captured by a sensors in a digital camera, may be corrected for this non-linear relationship of light and voltage. The red, green, and blue (R,G,B) components of a pixel may each be separately corrected. This correction uses a gamma-correction function that is complementary to the distortion function (above). The uncorrected captured pixel w is gamma-corrected to generate corrected pixel wxe2x80x2 using the following equation:
wxe2x80x2=wxcex1
where xcex1 is the reciprocal of gamma, 1/xcex3.
Many methods for gamma correction are known, both using analog and using digital techniques. For computer and digital camera systems, digital techniques are preferred since they are easier to integrate with the other digital functions.
Power functions such as the gamma-correction function have a special kind of symmetry that can be used to simplify implementation of the function. This symmetry depends on ratios. FIG. 1 shows a graph of a gamma-correction function that is divided into segments that are ratios of each other.
The gamma function graph has an input shown on the x axis that is normalized to be between 0 and 1. The output of the function is the y value of the curve at any desired x value. The y value can be read from the y axis. The curve for a power function such as a gamma correction function has the general curved shape shown.
The function curve is divided into several segments X0, X1, X2 . . . X5. The largest segment X0 is on the right and covers input x values from 0.5 to 1. The next segment X1 is half the width of segment X0, having inputs from 0.25 to 0.5. The third segment X2 is even smaller in width, having inputs from 0.125 to 0.25. Each successive segment has one-half the width of the segment to its right. The last (leftmost) segment X5 spans the range of 0 to 1/64.
The segments are thus related to each other by a ratio relationship. The segments are ratio-metrically related. The gamma function is a self-similar function because the function curve is similar in each of the segments. The function curve within each segment can be approximated as a straight line so that the gamma correction function is approximated as a piece-wise-linear (PWL) function. A non-linear correction can also be added to the PWL function. See U.S. Pat. No. 5,408,267 Main and assigned to The 3DO Company of Redwood City, Calif.
Rather than store the function curve for each of the segments, only the curve in the first (largest) segment X0 can be stored. This first segment X0 is known as the standard segment. When the input value is in one of the other segments, the input value is mapped (scaled up) to the range of the largest (standard) segment. Then the function curve of the standard segment is used to determine the y value. The y value is then de-mapped (scaled down) to the final output y that corresponds to the original (smaller) segment. This way only function values within the largest (standard) segment need to be stored or generated. The results from the largest segment are then scaled by the ratio of the segments raised to the power of xcex1.
FIG. 2 shows segments being mapped to the standard segment. In this example, the input value is encoded by 12 binary bits, so that the input can represent any value from 0 to 1 with a resolution of 1/4096. The largest segment X0 spans the range of inputs from 1/2 to 1. This is the standard segment. The next segment X2 spans inputs from 1/4 to 1/2, while the next segment X2 spans 1/8 to 1/4. Each successive segment spans half the width of inputs as the previous, until the smallest segment, X12, spans values from 0 to 1/4096, having only 2 values in the smallest segment.
When an input is in one the smaller segments X12 to X1, the input is scaled up to the input range of the standard segment X0 by a bit-shift. For example, to scale from segment X1 to X0, the input x is left-shifted by one bit-position, effectively multiplying by 2. To scale from segment X3 to X0, the input x is left-shifted by three bit-positions, effectively multiplying by 23 or 8. Inputs in segment X3 are thus shifted from the range of 1/16 to 1/8 to the range of 1/2 to 1. Inputs in the last segment X12 are shifted by 12 bits, or multiplied by 212 or 4096.
FIG. 3 is a table of segments in a prior-art gamma-correction function having 12 input bits. The 13 segments X0 to X12 have input ranges that double for each larger segment. For example, segment X5 has inputs in the range 1/64 to 1/32, which is double the width of the prior segment X6, which has inputs from 1/128 to 1/64.
The segment for any input x can be determined by a priority encoder. The priority encoder finds the bit-position of the leading one in the 12-bit input x. When the leading bit is a one, the priority encoder outputs a 0, indicating that the input is in the range of segment X0. When the priority encoder finds the leading one in the 6th bit position from the left, it outputs a 5 to indicate that the input is in the input range for segment X5, 1/64 to 1/32.
FIG. 4 is a diagram of gamma correction using segment mapping. The input pixel component, either the R, G, or B value, is applied to priority encoder 12. The leading one is detected and encoded by priority encoder 12 as a shift value N. Signal N indicates the number of bit positions from the left that the first (leading) one is located at within input x.
Mapper 10 also receives the input x, and shifts x by the number N of bit positions from priority encoder 12. The value of N indicates which segment the input x is in, as shown in the table of FIG. 3. Shifting input x by this number of bits maps the input x to the range of the standard segment, producing shifted input y.
The shifted input y from mapper 10 is sent to gamma corrector 14. Gamma corrector 14 accepts inputs only in the range of the standard segment. Gamma corrector 14 performs a linear interpolation within the standard segment to produce a corrected value yxe2x80x2. The corrected value yxe2x80x2 is a linear approximation of the gamma-correction curve within the standard segment. A non-linear correction may also be applied by gamma corrector 14.
Since the corrected value yxe2x80x2 from gamma corrector 14 is for the function curve within the standard segment, it needs to be scaled down to the function value for the actual segment of input x. De-mapper 16 multiplies the corrected value yxe2x80x2 from gamma corrector 14 by a pre-determined constant. This multiply scales the corrected value yxe2x80x2 to the corrected value xxe2x80x2 that corresponds to the input x.
While such segment-mapping gamma correction is useful, a large number of segments may be required for higher-precision graphics that use multi-bit pixels. For example, a 12-bit input x requires 13 segments to properly cover the entire input range with high precision. This requires the use of a 13-bit priority encoder and storage of 13 predefined constants for de-mapping. Such large priority encoders consume chip area and power. A smaller priority encoder is more desirable.
What is desired is a gamma corrector that uses segment mapping. It is desired to reduce the cost of the gamma correction system by reducing the amount of logic required for a large multi-bit priority encoder. The precision from a large number of segments is still desired, but with a lower logic burden. High precision while using a small priority encoder is desired. Multiplication by a reduced set of constants is desired to reduce constant storage. An efficient structure for a gamma correction apparatus using segment mapping is desired.
A multi-level segment-mapping function generator has an input with an input value within an input range. The input range is divided into a plurality of first-level segments of varying width including a standard first-level segment.
A first-level mapper receives the input value. It scales the input value to an intermediate input value within a range of the standard first-level segment. The first-level mapper outputs the intermediate input value to an intermediate input. The intermediate input value output by the first-level mapper is within a second input range equal to the range of the standard first-level segment. The range of the standard first-level segment is divided into a plurality of second-level segments of varying width. The plurality of second-level segments include a standard second-level segment.
A second-level mapper receives the intermediate input from the first-level mapper. It scales the intermediate input value to generate a final input value. The final input value is within a range of the standard second-level segment.
A function generator receives the final input from the second-level mapper. It generates a result of a pre-determined function from the final input value.
A second-level de-mapper receives the result from the function generator. It adjusts the result from the function generator to an intermediate result. The intermediate result is a result of the pre-determined function for the intermediate input value.
A first-level de-mapper receives the intermediate result from the second-level de-mapper. It adjusts the intermediate result from the second-level de-mapper to a final result. The final result is a result of the pre-determined function for the input value. Thus the final result can be generated for any input value within the input range using the function generator that generates results only within the standard second-level segment.
In further aspects the plurality of first-level segments are non-overlapping and ratio-metrically related where each smaller first-level segment is 1/a the input width of a next larger first-level segment. The constant a is a positive integer representing a first ratio. The standard first-level segment is a largest of the plurality of first-level segments.
The plurality of second-level segments are non-overlapping and ratio-metrically related where each smaller second-level segment is 1/b the input width of a next larger second-level segment, where b is a positive integer representing a second ratio. The standard second-level segment is a largest of the plurality of second-level segments. Thus segments are ratios of larger segments in a level.
In still further aspects the constant a is not equal to b. Each level has segments with different ratios of segment widths.
In further aspects of the invention the function generator is a linear interpolator generating the result by multiplying the final input by a slope of a line and adding a constant. Thus the function is approximated by a line within the standard second-level segment.
In further aspects the first-level mapper has a first priority encoder that receives the input. It detects a leading significant bit in multiple bits in the input that represent the input value. The first priority encoder generates a first shift signal determined by a location of the leading significant bit within the input value. A first shifter receives the input. It shifts the input value by a shift signal determined by the first shift signal to generate the intermediate input value. Thus the first-level mapper shifts the input value.
In other aspects the second-level mapper has a second priority encoder that receives the intermediate input. It detects a leading significant bit in multiple bits in the intermediate input that represent the intermediate input value. The second priority encoder generates a second shift signal determined by a location of the leading significant bit within the intermediate input value. A second shifter receives the intermediate input. It shifts the intermediate input value by a second shift signal determined by the second shift signal to generate the final input value. Thus the second-level mapper shifts the intermediate input value.
In still further aspects of the invention the first-level de-mapper has a reverse shifter that receives the intermediate result from the second-level de-mapper. It shifts the intermediate result by a number of bit-positions to generate the final result. The number of bit-positions is determined by the first shift signal from the first-level priority encoder. A full multiplier for multiplying the intermediate result by an arbitrary constant is not required. The reverse shifter shifts the intermediate result in an opposite direction to a direction that the first shifter shifts the input value.
In other aspects the second-level de-mapper has a constant multiplier that receives the result from the function generator. It multiplies the result by a constant to generate the intermediate result. The constant is a function of the second shift signal from the second priority encoder.